已知n*n矩阵A，A+A^2+A^3+...+A^k怎么求？

来源：百度知道 编辑：UC知道 时间：2024/06/04 03:21:34
如题，要求是logN复杂度，请写出源代码或者详细解释过程~感激不尽！
的确是有这么一个算法的，但是我看不懂，师兄说这样算：
A
A+A^2
A+A^2+A^3+A^4
A+A^2+A^3+A^4+A^5+A^6+A^7+A^8
这样每次乘以A的一个幂就能搞定，但是我看不懂。。。

个人觉得比较难。你这个也太省了。
正常矩阵乘法是N^3的复杂度，用一些特殊的方法，可能会降一些。

令S1 = E + A
S2 = S1 + A^2*S1;
S3 = S2 + A^4*S2;
..........
Sk = S(k-1) + A^(2^(k-1))*S(k-1).
令T = A^(2^(k-1))；
每次计算只需求出 T^2 和 T^2*S(k-1)；
这样用log(n)的时间求得最大的前2^m项(m为满足条件2^m<=n)；
对于后面的n-2^m项，提出公因式A^(2^m) 则剩下A + A^2+...+A^(n1)项且n1 < 2^m;
利用上述的方法继续需求。